package com.learn.algorithm_141;

import com.dataconsruct.ListNode;
import org.junit.Test;

/**
 * 求环形链表环的长度（即入环后，两次相遇之间的长度）
 * https://leetcode-cn.com/problems/linked-list-cycle/
 *
 * @author gatts, 2022/2/7 11:00
 */
public class CycleLengthListNode {

    @Test
    public void test() {
        ListNode head = new ListNode(3);
        ListNode first = new ListNode(2);
        ListNode second = new ListNode(0);
        ListNode third = new ListNode(-4);

        head.next = first;
        first.next = second;
        second.next = third;
        third.next = first;

        System.out.println(hasCycle(head));
    }

    /**
     * 快慢指针，快指针每次移动两步，慢指针每次一步
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        if (slow == null || fast == null) {
            return false;
        }
        int count = 0;
        while (slow != fast) {
            // 龟兔赛跑开始，非环形链表必然会有终点为null
            if (slow == null || fast == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            count++;
        }
        // 环形链表必然出现快慢指针是相同节点的时刻
        System.out.println("首次重合：" + count);

        slow = slow.next;
        fast = fast.next.next;
        count++;

        while (slow != fast) {
            // 龟兔赛跑开始，非环形链表必然会有终点为null
            if (slow == null || fast == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            count++;
        }
        System.out.println("再次重合：" + count);

//        System.out.println("环长度：" + );

        return true;
    }


}
